#include "StdAfx.h"
#include "Half_thinning_Algorithm.h"


int Half_thinning_Algorithm::N[3][3] =	{	{128,1,2},
									{64, 0, 4},
									{32, 16, 8}
								};

int Half_thinning_Algorithm::A0[48] =	{	3, 6, 7, 12, 14, 15, 24,
								28, 30, 31, 48, 56, 60, 62,
								63, 96, 112, 120, 124, 126,	127,
								129, 131, 135, 143, 159, 191, 192,
								193, 195, 199, 207, 223, 224, 225,
								227, 231, 239, 240, 241, 243, 247,
								248, 249, 251, 252, 253, 254
							};

Half_thinning_Algorithm::Half_thinning_Algorithm(void)
{
	this->runlength_hash_table = NULL;
}

int Half_thinning_Algorithm::calculate_estimated_stroke_width(IplImage *source)
{
	int width = 0;
	// Search borders
	this->marking_borders(source);
	int L = (int) this->borders.size();
	int N = 0;
	for (int y = 0; y < source->height; y++)
	{
		for (int x = 0; x < source->width; x++)
		{
			// Creating masks for image pixel
			if (((uchar *)(source->imageData + y * source->widthStep))[x] == 0)
			{
				N++;
			}
		}
	}

	width = (int) floor(((2.0 * N) / L)); 
	return width;
}

void Half_thinning_Algorithm::run(IplImage *source)
{
	// Remove spurious loops
	this->remove_spurious_loops(source);

	// Create mask
	int** mask = new int * [3];
			
	for (int k = -1; k < 2; k++)
	{
		mask[k+1] = new int [3];
	}

	bool isModified = false;

	do
	{
		isModified = false;
		vector<CvPoint> deleted_points;

		// First subiteration

		// Search borders
		this->marking_borders(source);

		for (int j = 0; j < (int) this->borders.size(); j++)
		{
			int x = this->borders[j].second;
			int y = this->borders[j].first;
		
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						mask[k+1][l+1] = 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						mask[k+1][l+1] = pixel_value;
					}
				}
			}

			// Check conditions of first subiteration
			if (this->check_first_condition(mask) && this->check_third_condition(mask) && this->check_fourth_condition(mask))
			{
				if ((this->check_second_condition(mask) == 1) || (this->check_second_condition(mask) == 2))
				{
					if (this->check_second_condition(mask) == 2)
					{
						if (this->check_seventh_condition(mask))
						{
							//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
							deleted_points.push_back(cvPoint(x,y));
							isModified = true;
						}
					}
					else
					{
						//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
						deleted_points.push_back(cvPoint(x,y));
						isModified = true;
					}
				}

			}
		}

		for(int ipt = 0; ipt <(int) deleted_points.size(); ipt++)
		{
			CvPoint point = deleted_points[ipt];
			((uchar *)(source->imageData + point.y * source->widthStep))[point.x] = 255;
		}
		
		deleted_points.clear();

		// Second subiteration
		for (int j = 0; j < (int) this->borders.size(); j++)
		{
			int x = this->borders[j].second;
			int y = this->borders[j].first;
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						mask[k+1][l+1] = 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						mask[k+1][l+1] = pixel_value;
					}
				}
			}
			// Check conditions of second subiteration
			if (this->check_first_condition(mask) && this->check_fifth_condition(mask) && this->check_sixth_condition(mask))
			{
				if ((this->check_second_condition(mask) == 1) || (this->check_second_condition(mask) == 2))
				{
					if (this->check_second_condition(mask) == 2)
					{
						if(this->check_eighth_condition(mask))
						{
							//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
							deleted_points.push_back(cvPoint(x,y));
							isModified = true;
						}
					}
					else
					{
						//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
						deleted_points.push_back(cvPoint(x,y));
						isModified = true;
					}
				}
			}
		}

		for(int ipt = 0; ipt <(int) deleted_points.size(); ipt++)
		{
			CvPoint point = deleted_points[ipt];
			((uchar *)(source->imageData + point.y * source->widthStep))[point.x] = 255;
		}

		this->borders.clear();
	}
	while(isModified);

	// Delete mask
	for (int k = 0; k < 3; k++)
	{
		delete [] mask[k];
	}
	delete [] mask;	

	return;
}

void Half_thinning_Algorithm::run_half_thinning(IplImage *source)
{
	// Remove spurious loops
	this->remove_spurious_loops(source);

	int hash_table_size = max((int) source->width, (int) source->height) + 1;
	this->runlength_hash_table = new int [hash_table_size];
	for (int i = 0; i< hash_table_size; i++)
	{
		this->runlength_hash_table[i] = 0;
	}
	this->scan_horizontal(source);
	this->scan_vertical(source);
	
	int max_frequent = 0;
	int stroke_average_width = 0;
	for (int i = 0; i< hash_table_size; i++)
	{
		if (max_frequent < runlength_hash_table[i])
		{
			max_frequent = runlength_hash_table[i];
			stroke_average_width = i;
		}
	}

	// Create mask
	int** mask = new int * [3];
			
	for (int k = -1; k < 2; k++)
	{
		mask[k+1] = new int [3];
	}

	for (int i = 0; i< (int) ceil(stroke_average_width * 1.0 / 2) ; i++)
	{
		vector<CvPoint> deleted_points;
		// First subiteration

		// Search borders
		this->marking_borders(source);

		for (int j = 0; j < (int) this->borders.size(); j++)
		{
			int x = this->borders[j].second;
			int y = this->borders[j].first;
		
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						mask[k+1][l+1] = 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						mask[k+1][l+1] = pixel_value;
					}
				}
			}

			// Check conditions of first subiteration
			if (this->check_first_condition(mask) && this->check_third_condition(mask) && this->check_fourth_condition(mask))
			{
				if ((this->check_second_condition(mask) == 1) || (this->check_second_condition(mask) == 2))
				{
					if (this->check_second_condition(mask) == 2)
					{
						if (this->check_seventh_condition(mask))
						{
							//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
							deleted_points.push_back(cvPoint(x,y));
						}
					}
					else
					{
						//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
						deleted_points.push_back(cvPoint(x,y));
					}
				}
			}
		}
		
		for(int ipt = 0; ipt <(int) deleted_points.size(); ipt++)
		{
			CvPoint point = deleted_points[ipt];
			((uchar *)(source->imageData + point.y * source->widthStep))[point.x] = 255;
		}

		deleted_points.clear();

		/*this->marking_borders(source);*/

		// Second subiteration
		for (int j = 0; j < (int) this->borders.size(); j++)
		{
			int x = this->borders[j].second;
			int y = this->borders[j].first;
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						mask[k+1][l+1] = 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						mask[k+1][l+1] = pixel_value;
					}
				}
			}
			// Check conditions of second subiteration
			if (this->check_first_condition(mask) && this->check_fifth_condition(mask) && this->check_sixth_condition(mask))
			{
				if ((this->check_second_condition(mask) == 1) || (this->check_second_condition(mask) == 2))
				{
					if (this->check_second_condition(mask) == 2)
					{
						if(this->check_eighth_condition(mask))
						{
							//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
							deleted_points.push_back(cvPoint(x,y));
						}
					}
					else
					{
						//((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
						deleted_points.push_back(cvPoint(x,y));
					}
				}
			}
		}

		for(int ipt = 0; ipt <(int) deleted_points.size(); ipt++)
		{
			CvPoint point = deleted_points[ipt];
			((uchar *)(source->imageData + point.y * source->widthStep))[point.x] = 255;
		}

		this->borders.clear();
	}

	// Delete mask
	for (int k = 0; k < 3; k++)
	{
		delete [] mask[k];
	}
	delete [] mask;	

	return;
}


void Half_thinning_Algorithm::scan_horizontal(IplImage *source)
{
	for (int i = 0; i < (int) source->height; i++)
	{
		int runlength = 0;
		for (int j = 0; j < (int) source->width; j++)
		{
			if (((uchar *)(source->imageData + i * source->widthStep))[j] == 0)
			{
				runlength++;
			}
			else
			{
				if (runlength > 0)
				{
					this->runlength_hash_table[runlength]++;
				}
				runlength = 0;
			}
		}
	}
	return;
}

void Half_thinning_Algorithm::scan_vertical(IplImage *source)
{
	for (int j = 0; j < (int) source->width; j++)
	{
		int runlength = 0;
		for (int i = 0; i < (int) source->height; i++)
		{
			if (((uchar *)(source->imageData + i * source->widthStep))[j] == 0)
			{
				runlength++;
			}
			else
			{
				if (runlength > 0)
				{
					this->runlength_hash_table[runlength]++;
				}
				runlength = 0;
			}
		}
	}
	return;
}

void Half_thinning_Algorithm::marking_borders(IplImage *source)
{
	this->borders.clear();
	int** mask = new int * [3];
			
	for (int k = -1; k < 2; k++)
	{
		mask[k+1] = new int [3];
	}

	for (int y = 0; y < source->height; y++)
	{
		for (int x = 0; x < source->width; x++)
		{
			// Creating masks for image pixel
			if (((uchar *)(source->imageData + y * source->widthStep))[x] == 0)
			{
				int neighbourhood_weight = 0;
				for (int k = -1; k < 2; k++)
				{
					for (int l = -1; l < 2; l++)
					{
						if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
						{
							mask[k+1][l+1] = 0;
						}
						else
						{
							uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
							mask[k+1][l+1] = pixel_value;
						}
					}
				}
			
				if (this->check_border_condition(mask))
				{
					this->borders.push_back(make_pair(y,x));
				}
			}
			
		}
	}

	// Delete mask
	for (int k = 0; k < 3; k++)
	{
		delete [] mask[k];
	}
	delete [] mask;
	return;
}

bool Half_thinning_Algorithm::check_border_condition(int** mask)
{
	int sum = 0;
	int product = 0;
	int ordered_set[8] = {mask[0][1],mask[0][2],mask[1][2],mask[2][2],mask[2][1],mask[2][0],mask[1][0],mask[0][0]};
	for (int i = 0; i< 8; i++)
	{
		product*= ordered_set[i];
		sum+= ordered_set[i];
	}
	if (sum > 0)
	{
		if (mask[0][1] * mask[1][2] * mask[2][1] * mask[1][0] == 0)
		{
			return true;
		}
	}
	return false;
}

bool Half_thinning_Algorithm::check_first_condition(int** mask)
{
	int B = 0;
	int ordered_set[8] = {mask[0][1],mask[0][2],mask[1][2],mask[2][2],mask[2][1],mask[2][0],mask[1][0],mask[0][0]};
	for (int i = 0; i< 8; i++)
	{
		B+= ordered_set[i];
	}
	if ((B >= 2) && (B <= 6))
	{
		return true;
	}
	else
	{
		return false;
	}
}

int Half_thinning_Algorithm::check_second_condition(int** mask)
{
	int A = 0;
	int ordered_set[9] = {mask[0][1],mask[0][2],mask[1][2],mask[2][2],mask[2][1],mask[2][0],mask[1][0],mask[0][0], mask[0][1]};
	for (int i = 0; i< 8; i++)
	{
		if ((ordered_set[i] == 0) && (ordered_set[i+1] == 1))
		{
			A++;
		}
	}
	return A;
}

bool Half_thinning_Algorithm::check_third_condition(int** mask)
{
	if (mask[0][1] * mask[1][2] * mask[2][1] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool Half_thinning_Algorithm::check_fourth_condition(int** mask)
{
	if (mask[1][2] * mask[2][1] * mask[1][0] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool Half_thinning_Algorithm::check_fifth_condition(int** mask)
{
	if (mask[0][1] * mask[1][2] * mask[1][0] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool Half_thinning_Algorithm::check_sixth_condition(int** mask)
{
	if (mask[0][1] * mask[2][1] * mask[1][0] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool Half_thinning_Algorithm::check_seventh_condition(int** mask)
{
	bool condition_a = false;
	bool condition_b = false;
	condition_a = ((mask[1][2] * mask[2][1]) == 1) && ((mask[0][2] + mask[2][0]) != 0) /*&& ((mask[0][2] * mask[2][0]) == 0)*/ && ((mask[0][1] + mask[0][0] + mask[1][0] + mask[2][2]) == 0);
	condition_b = ((mask[1][2] * mask[0][1]) == 1) && ((mask[0][0] + mask[2][2]) != 0) /*&& ((mask[0][0] * mask[2][2]) == 0)*/ && ((mask[0][2] + mask[1][0] + mask[2][0] + mask[2][1]) == 0);
	return (condition_a || condition_b);
}

bool Half_thinning_Algorithm::check_eighth_condition(int** mask)
{
	bool condition_a = false;
	bool condition_b = false;
	condition_a = ((mask[0][1] * mask[1][0]) == 1) && ((mask[0][0] + mask[2][2]) != 0) /* && ((mask[0][0] * mask[2][2]) == 0)*/ && ((mask[1][2] + mask[0][2] + mask[2][0] + mask[2][1]) == 0);
	condition_b = ((mask[1][0] * mask[2][1]) == 1) && ((mask[0][2] + mask[2][0]) != 0) /* && ((mask[0][2] * mask[2][0]) == 0)*/ && ((mask[1][2] + mask[0][1] + mask[0][0] + mask[2][2]) == 0);
	return (condition_a || condition_b);
}

void Half_thinning_Algorithm::remove_spurious_loops(IplImage *source)
{
	// Template 1
	int** mask = new int * [3];
			
	for (int k = -1; k < 2; k++)
	{
		mask[k+1] = new int [3];
	}


	for (int i = 1; i< (int) source->height - 1; i++)
	{
		for (int j = 1; j < (int) source->width - 1; j++)
		{
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					uchar pixel_value = (((uchar *)(source->imageData + (i + k) * source->widthStep))[j + l] == 255) ? 0 : 1;
					mask[k+1][l+1] = 1 - pixel_value;
					if ((k == 0) && (l == 0))
					{
						mask[k+1][l+1] = pixel_value;
					}
				}
			}

			if ((mask[0][1] + mask[1][0] + mask[1][1] + mask[1][2] +  mask[2][1]) == 0)
			{
				if (mask[0][0] == 1)
				{
					((uchar *)(source->imageData + (i - 1) * source->widthStep))[j] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j - 1] = 255;
				}
				else if (mask[0][2] == 1)
				{
					((uchar *)(source->imageData + (i - 1) * source->widthStep))[j] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j + 1] = 255;

				}
				else if (mask[2][0] == 1)
				{
					((uchar *)(source->imageData + (i) * source->widthStep))[j - 1] = 255;
					((uchar *)(source->imageData + (i + 1) * source->widthStep))[j] = 255;
				}
				else if (mask[2][2] == 1)
				{
					((uchar *)(source->imageData + (i + 1) * source->widthStep))[j] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j + 1] = 255;
				}
			}
		}
	}

	// Delete mask
	for (int k = 0; k < 3; k++)
	{
		delete [] mask[k];
	}
	delete [] mask;

	// Template 2
	mask = new int * [3];
			
	for (int k = -1; k < 2; k++)
	{
		mask[k+1] = new int [4];
	}
	for (int i = 1; i< (int) source->height - 1; i++)
	{
		for (int j = 1; j < (int) source->width - 2; j++)
		{
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 3; l++)
				{
					uchar pixel_value = (((uchar *)(source->imageData + (i + k) * source->widthStep))[j + l] == 255) ? 0 : 1;
					mask[k+1][l+1] = 1 - pixel_value;
					if (((k == 0) && (l == 0)) || ((k == 0) && (l == 1)))
					{
						mask[k+1][l+1] = pixel_value;
					}
				}
			}

			if ((mask[0][1] + mask[1][0] + mask[1][1] + mask[1][2] +  mask[2][1] + mask[0][2] + mask[1][3] + mask[2][2]) == 0)
			{
				if (mask[0][0] == 1)
				{
					((uchar *)(source->imageData + (i - 1) * source->widthStep))[j] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j - 1] = 255;
				}
				else if (mask[0][3] == 1)
				{
					((uchar *)(source->imageData + (i - 1) * source->widthStep))[j+1] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j + 2] = 255;

				}
				else if (mask[2][0] == 1)
				{
					((uchar *)(source->imageData + (i) * source->widthStep))[j - 1] = 255;
					((uchar *)(source->imageData + (i + 1) * source->widthStep))[j] = 255;
				}
				else if (mask[2][3] == 1)
				{
					((uchar *)(source->imageData + (i + 1) * source->widthStep))[j + 1] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j + 2] = 255;
				}
			}
		}
	}

	// Delete mask
	for (int k = 0; k < 3; k++)
	{
		delete [] mask[k];
	}
	delete [] mask;

	// Template 2
	mask = new int * [4];
			
	for (int k = -1; k < 3; k++)
	{
		mask[k+1] = new int [3];
	}
	for (int i = 1; i< (int) source->height - 2; i++)
	{
		for (int j = 1; j < (int) source->width - 1; j++)
		{
			for (int k = -1; k < 3; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					uchar pixel_value = (((uchar *)(source->imageData + (i + k) * source->widthStep))[j + l] == 255) ? 0 : 1;
					mask[k+1][l+1] = 1 - pixel_value;
					if (((k == 0) && (l == 0)) || ((k == 1) && (l == 0)))
					{
						mask[k+1][l+1] = pixel_value;
					}
				}
			}

			if ((mask[0][1] + mask[1][0] + mask[1][1] + mask[1][2] +  mask[2][1] + mask[2][0] + mask[3][1] + mask[2][2]) == 0)
			{
				if (mask[0][0] == 1)
				{
					((uchar *)(source->imageData + (i - 1) * source->widthStep))[j] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j - 1] = 255;
				}
				else if (mask[0][2] == 1)
				{
					((uchar *)(source->imageData + (i - 1) * source->widthStep))[j] = 255;
					((uchar *)(source->imageData + (i) * source->widthStep))[j + 1] = 255;

				}
				else if (mask[3][0] == 1)
				{
					((uchar *)(source->imageData + (i + 1) * source->widthStep))[j - 1] = 255;
					((uchar *)(source->imageData + (i + 2) * source->widthStep))[j] = 255;
				}
				else if (mask[3][2] == 1)
				{
					((uchar *)(source->imageData + (i + 1) * source->widthStep))[j + 1] = 255;
					((uchar *)(source->imageData + (i + 2) * source->widthStep))[j] = 255;
				}
			}
		}
	}

	// Delete mask
	for (int k = 0; k < 4; k++)
	{
		delete [] mask[k];
	}
	delete [] mask;

	return;
	return;
}

double Half_thinning_Algorithm::calculate_dc(int x, int y, IplImage *source)
{
	// Search borders
	this->marking_borders(source);
	double dc = 1000000.0;
	for (int i = 0; i< (int) this->borders.size(); i++)
	{
		int by = this->borders[i].first;
		int bx = this->borders[i].second;
		double distance = sqrt(((bx - x) * (bx - x) + (by - y) * (by - y)) * 1.0);
		if (distance < dc)
		{
			dc = distance;
		}
	}
	return dc;
}


Half_thinning_Algorithm::~Half_thinning_Algorithm(void)
{
	if (this->runlength_hash_table != NULL)
	{
		delete [] this->runlength_hash_table;
	}
}
